﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
//
//
//
//示例 1:
//
//输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
//输出 : [5, 6, 7, 1, 2, 3, 4]
//解释 :
//	向右轮转 1 步 : [7, 1, 2, 3, 4, 5, 6]
//	向右轮转 2 步 : [6, 7, 1, 2, 3, 4, 5]
//	向右轮转 3 步 : [5, 6, 7, 1, 2, 3, 4]
//	示例 2 :
//
//	输入：nums = [-1, -100, 3, 99], k = 2
//	输出：[3, 99, -1, -100]
//	解释 :
//	向右轮转 1 步 : [99, -1, -100, 3]
//	向右轮转 2 步 : [3, 99, -1, -100]

//一般解法：时间复杂度为o(n^2):
//void rotate(int* nums, int numsSize, int k) {
//    k = k % numsSize;
//    while (k--)
//    {
//        int tmp = nums[numsSize - 1];
//        int i = 0;
//        for (i = numsSize - 1; i >= 1; i--)
//        {
//            nums[i] = nums[i - 1];
//        }
//        nums[0] = tmp;
//    }
//}

//最优解法：时间复杂度为o(n):
//void Turn_arr(int* arr, int start, int end)
//{
//    int l = start, r = end - 1;
//    while (l < r)
//    {
//        int tmp = arr[l];
//        arr[l] = arr[r];
//        arr[r] = tmp;
//        l++;
//        r--;
//    }
//}
//void rotate(int* nums, int numsSize, int k) {
//    k = k % numsSize;
//    Turn_arr(nums, 0, numsSize);
//    Turn_arr(nums, 0, k);
//    Turn_arr(nums, k, numsSize);
//}
void Turn_arr(int* nums, int l, int r) {
    while (l < r) {
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
        l++;
        r--;
    }
}
void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    Turn_arr(nums, 0, numsSize - k - 1);
    Turn_arr(nums, numsSize - k, numsSize-1);
    Turn_arr(nums, 0, numsSize-1);
}
int main()
{
    int arr[] = { 1,2,3,4,5,6,7 };
    rotate(arr, 7, 3);
    int i;
    for (i = 0; i < 7; i++)
    {
        printf("%d", arr[i]);
    }
	return 0;
}